$$\newcommand{\xv}{\mathbf{x}} \newcommand{\Xv}{\mathbf{X}} \newcommand{\yv}{\mathbf{y}} \newcommand{\Yv}{\mathbf{Y}} \newcommand{\zv}{\mathbf{z}} \newcommand{\av}{\mathbf{a}} \newcommand{\Wv}{\mathbf{W}} \newcommand{\wv}{\mathbf{w}} \newcommand{\betav}{\mathbf{\beta}} \newcommand{\gv}{\mathbf{g}} \newcommand{\Hv}{\mathbf{H}} \newcommand{\dv}{\mathbf{d}} \newcommand{\Vv}{\mathbf{V}} \newcommand{\vv}{\mathbf{v}} \newcommand{\Uv}{\mathbf{U}} \newcommand{\uv}{\mathbf{u}} \newcommand{\tv}{\mathbf{t}} \newcommand{\Tv}{\mathbf{T}} \newcommand{\Sv}{\mathbf{S}} \newcommand{\Gv}{\mathbf{G}} \newcommand{\zv}{\mathbf{z}} \newcommand{\Zv}{\mathbf{Z}} \newcommand{\Norm}{\mathcal{N}} \newcommand{\muv}{\boldsymbol{\mu}} \newcommand{\sigmav}{\boldsymbol{\sigma}} \newcommand{\phiv}{\boldsymbol{\phi}} \newcommand{\Phiv}{\boldsymbol{\Phi}} \newcommand{\Sigmav}{\boldsymbol{\Sigma}} \newcommand{\Lambdav}{\boldsymbol{\Lambda}} \newcommand{\half}{\frac{1}{2}} \newcommand{\argmax}[1]{\underset{#1}{\operatorname{argmax}}} \newcommand{\argmin}[1]{\underset{#1}{\operatorname{argmin}}} \newcommand{\dimensionbar}[1]{\underset{#1}{\operatorname{|}}} \newcommand{\grad}{\mathbf{\nabla}} \newcommand{\ebx}[1]{e^{\betav_{#1}^T \xv_n}} \newcommand{\eby}[1]{e^{y_{n,#1}}} \newcommand{\Tiv}{\mathbf{Ti}} \newcommand{\Fv}{\mathbf{F}} \newcommand{\ones}[1]{\mathbf{1}_{#1}} $$

Introduction to Reinforcement Learning

Concepts

Imagine a position in a tic-tac-toe game (knots and crosses). How do you choose the best next action?

Which are you most likely to win from? Guess at how likely you are to win from each state. Is a win definite, likely, or maybe?

States and Actions

Set of possible states, $\mathcal{S}$.

• Can be discrete values ($|\mathcal{S}| < \infty$)
  • Tic-Tac-Toe game positions
  • Position in a maze
  • Sequence of steps in a plan
• Can be continuous values ($|\mathcal{S}| = \infty$)
  • Joint angles of a robot arm
  • Position and velocity of a race car
  • Parameter values for a network routing strategy

Set of possible actions, $\mathcal{A}$.

• Can be discrete values ($|\mathcal{A}| < \infty$)
  • Next moves in Tic-Tac-Toe
  • Directions to step in a maze
  • Rearrangements of a sequence of steps in a plan
• Can be continuous values ($|\mathcal{A}| = \infty$)
  • Torques to apply to the joints of a robot arm
  • Fuel rate and turning torque in a race car
  • Settings of parameter values for a network routing strategy

Values

We want to choose the action that we predict will result in the best possible future from the current state. Need a value that represents the future outcome.

What should the value represent?

• Tic-Tac-Toe: Likelihood of winning from a game position.
• Maze: Number of steps to reach the goal.
• Plan: Efficiency in time and cost of accomplishing the objective for particular rearrangment of steps in a plan.
• Robot: Energy required to move the gripper on a robot arm to a destination.
• Race car: Time to reach the finish line.
• Network routing: Throughput.

With the correct values, multi-step decision problems are reduced to single-step decision problems. Just pick action with best value. Guaranteed to find optimal multi-step solution (dynamic programming).

The utility or cost of a single action taken from a state is the reinforcement for that action from that state. The value of that state-action is the expected value of the full return or the sum of reinforcements that will follow when that action is taken.

Say we are in state $s_t$ at time $t$. Upon taking action $a_t$ from that state we observe the one step reinforcement $r_{t+1}$, and the next state $s_{t+1}$.

Say this continues until we reach a goal state, $K$ steps later. What is the return $R_t$ from state $s_t$?

$$ \begin{align*} R_t = \sum_{k=0}^K r_{t+k+1} \end{align*} $$

Use the returns to choose the best action.

Right...are we maximizing or minimizing? What does the reinforcement represent? Let's say it is energy used that we want to minimize. $a_1$, $a_2$, or $a_3$?

Where do the values come from?

• Write the code to calculate them.
  • Usually not possible. If you can do this for your problem, why are you considering machine learning? Might be able to do this for Tic-Tac-Toe.
• Use dynamic programming.
  • Usually not possible. Requires knowledge of the probabilities of transitions between all states for all actions.
• Learn from examples, lots of examples. Lots of 5-tuples: state, action, reinforcement, next state, next action ($s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}$).
  • Monte Carlo: Assign to each state-action pair an average of the observed returns: $ \;\;\;\text{value}(s_t,a_t) \approx \text{mean of } R(s_t,a_t)$
  • Temporal Difference (TD): Using $\text{value}(s_{t+1},a_{t+1})$ as estimate of return from next state, update current state-action value: $\;\;\; \text{value}(s_t,a_t) \approx r_{t+1} + \text{value}(s_{t+1},a_{t+1})$

What is the estimate of the return $R$ from state B?

• Monte Carlo: $\text{mean of } R(s_t,a_t)$ = 1, a prediction of a win
• Temporal Difference (TD): $r_{t+1} + \text{value}(s_{t+1},a_{t+1}) = 0 + (100(-1) + 2(1))/100 = -0.98$, a very likely loss
• What do you do? The green pill or the red pill?
• TD takes advantage of the cached experience given in the value learned for State C.

Example: Maze

Here is a simple maze.

From any position, how do you decide whether to move up, right, down, or left?

Right. Need an estimate of the number of steps to reach the goal. This will be the return $R$. How do we formulate this in terms of reinforcements?

Yep. $r_t = 1$ for every step. Then $R_t = \sum_{k=0}^K r_{t+k+1}$ will sum of those 1's to produce the number of steps to goal from each state.

The Monte-carlo way will assign value as average of number of steps to goal from each starting state tried.

The TD way will update value based on (1 + estimated value from next state).

Should we do Monte-Carlo update or Temporal-Difference updates? Take a look at this comparison on the maze problem.

State-Action Value Function as a Table

Tabular Function

Recall that the state-action value function is a function of both state and action and its value is a prediction of the expected sum of future reinforcements.

We will call the state-action value function $Q$, after Learning from Delayed Rewards, by C. Watkins, PhD Thesis, University of Cambridge, Cambridge, UK, 1989.

We can select our current belief of what the optimal action, $a_t^o$, is in state $s_t$ by

$$ \begin{align*} a_t^o = \argmax{a} Q(s_t,a) \end{align*} $$

or

$$ \begin{align*} a_t^o = \argmin{a} Q(s_t,a) \end{align*} $$

Tabular Q for the Maze Problem

Representing the Q Table

For the maze world,

$$ \begin{align*} a_t^o = \argmin{a} Q(s_t,a) \end{align*} $$

looks like (argmax should be argmin)

A bit more mathematically, let the current state be given by position in $x$ and $y$ coordinates and actions are integers 1 to

1. Then

$$ \begin{align*} a_t^o = \argmin{a\in \{1,2,3,4\}} Q\left ((x,y), a\right ) \end{align*} $$

Now, let's try to do this in python.

How do we implement the Q function? For the maze problem, we know we can

• enumerate all the states (positions) the set of which is finite ($10\cdot 10$),
• enumerate all actions, the set of which is finite (4),
• calculate the new state from the old state and an action, and
• represent in memory all state-action combinations ($10\cdot 10\cdot 4$).

So, let's just store the Q function in table form.

The Q table will need three dimensions, for $x$, $y$, and the action.

How do we look up the Q values for a state?

Q values are steps to goal, so we are minimizing. Select right or down action.

We are finally ready for python. How can we make a three-dimensional table of Q values, if $x$ and $y$ have 10 possible values and we have 4 actions?

 import numpy as np
 Q = np.zeros((10,10,4))

How should we initialize the table? Above line initializes all values to be zero. What effect will this have as Q values for actions taken are updated to estimate steps to goal?

Actions not yet tried will have lowest (0) Q value. Forces the agent to try all actions from all states---lots of exploration.

Updating the Q Table Using Temporal-Difference Updates

What must we do after observing $s_t$, $a_t$, $r_{t+1}$, $s_{t+1}$, and $a_{t+1}$?

Calculate the temporal-difference error $r_{t+1} + Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)$ and use it to update the Q value stored for $s_t$ and $a_t$:

$$ \begin{align*} Q(s_t,a_t) = Q(s_t,a_t) + \rho (r_{t+1} + Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)) \end{align*} $$

And, in python? Assume position, or state, $(2,3)$ is implemented as ''state = np.array([2,3])''.

r = 1
Qold = Q[stateOld[0], stateOld[1], actionOld]
Qnew = Q[state[0], state[1], action]
TDError = r + Qnew - Qold
Q[stateOld[0], stateOld[1], actionOld] = Qold + rho * TDError

This is performed for every pair of steps $t$ and $t+1$, until the final step, which must be handled differently. There is no $s_{t+1}$. The update

$$ \begin{align*} Q(s_t,a_t) = Q(s_t,a_t) + \rho (r_{t+1} + Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)) \end{align*} $$

becomes

$$ \begin{align*} Q(s_t,a_t) = Q(s_t,a_t) + \rho (r_{t+1} - Q(s_t,a_t)) \end{align*} $$

In python, add a test for being at the goal. Let ''maze'' be character array containing a ''G'' at the goal position.

r = 1
Qold = Q[stateOld[0], stateOld[1], actionOld]
Qnew = Q[state[0], state[1], action]

if (maze[state[0]+1,state[1]+1] == 'G'):
    TDerror = r - Qold
else:
    TDerror = r + Qnew - Qold

Q[stateOld[0], stateOld[1], actionOld] = Qold + rho * TDerror

To choose the best action for state $(x, y)$ stored in variable state, just need to do

 a = np.argmin(Q[state[0],state[1],:])

and if we store the available actions as

 actions = np.array([[0,1],[1,0],[0,-1],[-1,0]])

then the update to state based on action a is done by

 state = state + actions[a,:]

The Agent-Environment Interaction Loop

For our agent to interact with its world, we must implement the steps

1. Initialize Q.
2. Choose random, non-goal, state.
3. Repeat:
   1. If at goal,
      1. Update Qold with TD error (1 - Qold)
      2. Pick new random state
   2. Otherwise (not at goal),
      1. Select next action.
      2. If not first step, update Qold with TD error (1 + Qnew - Qold)
      3. Shift current state and action to old ones.
      4. Apply action to get new state.

In Python it would look something like the following for a 10x10 maze.

 Q = np.zeros((10,10,4))                  # 1.
 s = np.random.randint(0,10,2)            # 2.
 for step in xrange(10000):               # 3. (or forever)
     if isGoal(s):                        # 3.A.
         Q[sOld[0],sOld[1],aOld] +=       # 3.A.a
              rho * (1 - Q[sOld[0],sOld[1],aOld])
         s = np.random.randint(0,10,2)    # 3.A.b
     else:                                # 3.B
         a = np.argmin(Q[s[0],s[1],:])    # 3.B.a
         if steps > 1:
             Q[sOld[0],sOld[1],aOld] +=   # 3.B.b
                  rho * (1 + Q[s[0],s[1],a] - Q[sOld[0],sOld[1],aOld])
         sOld, aOld = s, a                # 3.B.c
         s += actions[a,:]                # 3.B.d

Python Solution of the Maze Problem

First, we start with a text file that specifies a maze. Let's use the cell magic %%writefile to make the maze file.

Need some functions, one to draw the Q surface, over the two-dimensional state space (position in the maze), and one to select an action given the Q surface.

Construct arrays to hold the tabular Q values updated by temporal differences, and one to hold Q values updated by Monte Carlo. Set Q values to np.inf for invalid actions. We have four possible actions from each position.

Now for some parameters. Let's run for 50,000 interactions with maze environment, so 50,000 updates, and let $\rho$, the learning rate, be 0.1 and $\epsilon$, the random action probability, be 0.01.

Now we need to keep a history, or trace, of positions and reinforcement, to be used to update the MC version of Q.

Need some initializations before starting the loop.